#
# @lc app=leetcode.cn id=16 lang=python3
#
# [16] 最接近的三数之和
#

# @lc code=start
from typing import List


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 4:
            return sum(nums)
        nums.sort()
        ans = sum(nums[:3])
        minDiff = abs(ans - target)
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, len(nums) - 1

            result = nums[i] + nums[j] + nums[j + 1]
            diff = result - target
            if diff > 0:
                ans, minDiff = (result, abs(diff)) if abs(diff) < minDiff else (ans, minDiff)
                continue

            result = nums[i] + nums[k - 1] + nums[k]
            diff = result - target
            if diff < 0:
                ans, minDiff = (result, abs(diff)) if abs(diff) < minDiff else (ans, minDiff)
                continue

            while j < k:
                result = nums[i] + nums[j] + nums[k]
                diff = result - target
                if not diff:
                    return result
                ans, minDiff = (result, abs(diff)) if abs(diff) < minDiff else (ans, minDiff)
                if diff > 0:
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
                else:
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
        return ans


# @lc code=end
